package com.algorithm.classics150.链表;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 */
public class 删除链表的倒数第N个结点_19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null){
            return null;
        }
        //在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），
        // 它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
        ListNode dummyNode  = new ListNode();
        dummyNode.next = head;
        ListNode l1 = dummyNode;
        ListNode l2 = dummyNode;
        // 先让l2走n步，让l1和l2差n步
        for (int i = 0;i<n;i++){
            l2 = l2.next;
        }
        // 如果没走到最后开始两个一起走
        while (l2.next != null){
            l1 = l1.next;
            l2 = l2.next;
        }
        //走到之后直接删除操作
        l1.next = l1.next.next;
        return dummyNode.next;
    }
}
